#include <bits/stdc++.h>
using namespace std;

#define S64_t long long
#define U64_t unsigned long long
 
 
#define MAXN 1000
#define MAXW 1000
int f[MAXW], w[MAXN], c[MAXN];


int fullbag_v1(int n, int maxV, int *w, int *c, int *f)
{
   for(int i=1; i<=n; ++i)
      for(int j=0; j<=maxV; ++j)
         if(j - w[i] < 0) f[j] = max(f[j], f[j - w[i]] + c[i]);
   return f[maxV];
}

int main()
{
   int m, n;
   scanf("%d%d", &m, &n);
   for(int i=1; i<=n; ++i) scanf("%d%d", &w[i], &c[i]);
   for(int i=1; i<=n; ++i){
      for(int j=0; j<=m; j++){
         if(j-w[i]>=0){
            f[j] = max(f[j], f[j-w[i]]+c[i]);
         }
      }
   }
   printf("max=%d", f[m]);
   return 0;
}
